package test;
import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {
		int[] arr = {9, 1, 5, 0, 2, 4, 8, 6, 3, 7};
		
		sort1(arr, 1);
		
		System.out.println(Arrays.toString(arr));
	}
	
	public static void sort(int[] arr)
	{
		for(int j = 1; j < arr.length; j ++)
		{
			int i = j - 1;
			int value = arr[j];
			while(i >= 0 && value < arr[i])
			{
				arr[i + 1] = arr[i];
				i --;
			}
			
			arr[i + 1] = value;
		}
	}
	
	public static void sort1(int[] arr, int flag)
	{
		int i = flag - 1;
		int value = arr[flag];
		while(i >= 0 && value < arr[i])
		{
			arr[i + 1] = arr[i];
			i --;
		}
		
		arr[i + 1] = value;

		if(flag < arr.length - 1)
		{
			sort1(arr, flag + 1);
		}
	}
}
